#define DEBUG
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn=30, maxm=maxn*(maxn-1)/2, maxw=152501, mods=998244353;

int phi[maxw+1];

void initPhi(int n, int phi[]) {
	static int p[maxw+1];
	static bool book[maxw+1];
	phi[1] = 1;
	for (int i=2; i<=n; i++) {
		if (!book[i]) {
			p[++p[0]] = i;
			phi[i] = i-1;
		}
		for (int j=1; j<=p[0] && i*p[j]<=n; j++) {
			book[i*p[j]] = true;
			if (i%p[j]==0) {
				phi[i*p[j]] = phi[i]*p[j];
				break;
			} else {
				phi[i*p[j]] = phi[i]*phi[p[j]];
			}
		}
	}
}

int max(int a, int b) {
	return a<b ? a : b;
}

ll power(ll a, int n) {
	ll s=1;
	for (; n; n/=2) {
		if (n&1) s=s*a%mods;
		a=a*a%mods;
	}
	return s;
}

class Line {
	public:
		//b=x*a+y
		ll x, y;

		Line() {}
		Line(ll u, ll v) {
			x = u%mods, y = v%mods;
		}

		Line operator+(Line &b) {
			return Line(x+b.x, y+b.y);
		}

		Line operator-(Line &b) {
			return Line(x-b.x+mods, y-b.y+mods);
		}

		Line operator*(Line &b) {
			return Line(x*b.y%mods+y*b.x%mods, y*b.y);
		}

		Line operator/(Line &b) {
			return Line((x*b.y%mods+mods-b.x*y%mods)%mods*power(c*c%mods, mods-2), a*power(c, mods-2));
		}
};

int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);

	static int u[maxm+1], v[maxm+1], w[maxm+1];
	int n, m, mw=0;
	scanf("%d %d", &n, &m);
	for (int i=1; i<=m; i++) {
		scanf("%d %d %d", u+i, v+i, w+i);
		mw = max(mw, w);
	}

	initPhi(maxw, phi);
	static Line map[maxn+1][maxn+1];
	ll ans=0;
	for (int i=1; i<=mw; i++) {
		int cnt=0;
		for (int j=1; j<=m; j++) {
			if (w[j]%i==0) {
				cnt++;
				map[u[j]][v[j]]-=Line(w[j], 1), map[v[j]][u[j]]-=Line(w[j], 1);
				map[u[j]][u[j]]+=Line(w[j], 1), map[v[j]][v[j]]+=Line(w[j], 1);
			}
		}

		if (cnt>=n-1) {
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
